package BinaryTrees;

import java.util.Comparator;

import BinaryTrees.BinaryTree;

// 二叉搜索树
@SuppressWarnings("unchecked")
public class BSTree <E> extends BinaryTree<E> {
	private Comparator<E> comparator;

	public BSTree() {
		this(null);
	}

	public BSTree(Comparator<E> comparator) {
		this.comparator = comparator;
	}

	// 添加节点
	public void add(E element) {
		// 检查添加元素
		elementNoNullCheck(element);

		// 添加root节点
		if (root == null) {
			root = createNode(element, null);
			size++;
			
			// 新添加节点之后的处理(平衡二叉树处理)
			afterAdd(root);
			return;
		}

		// 添加的不是根节点
		// 找到父节点
		Node<E> node = root;
		Node<E> parent = root;
		int cmp = 0;
		do {
			cmp = compare(element, node.element);
			parent = node;
			if (cmp > 0) {
				node = node.right;
			} else if (cmp < 0) {
				node = node.left;
			} else {
				node.element = element;
				return;
			}

		} while (node != null);

		// 插入到父节点中
		Node<E> newNode = createNode(element, parent); 
		if (cmp > 0) {
			parent.right = newNode;
		} else {
			parent.left = newNode;
		}
		size++;
		// 新添加节点之后的处理(平衡二叉树处理)
		afterAdd(newNode);
	}
	
	// 新添加节点之后的处理(平衡二叉树处理)
	// 这里的二叉搜索树默认不处理,让子类的二叉平衡树去处理.
	protected void afterAdd(Node<E> node) { }
	
	// 删除节点之后的处理(平衡二叉树处理)
	// 这里的二叉搜索树默认不处理,让子类的二叉平衡树去处理.
	protected void afterRemove(Node<E> node) { }

	// 删除某个元素的节点
	public void remove(E element) {
		remove(node(element));
	}

	// 判断是否包含某个节点元素的节点
	public boolean contains(E elementE) {
		return node(elementE) != null;
	}

	private void remove(Node<E> node) {
		if (node == null) {
			return;
		}

		size--;

		if (node.hasTwoChildren()) { // 当前节点有两个子节点
			// 找到前驱/后继节点:
			// 01.将前驱/后继节点的赋值到当前节点
			// 02.删除前驱/后继节点
			Node<E> successorNode = successor(node);
			node.element = successorNode.element;
			// 将当前节点标记到后继节点位置,后续做删除操作.
			node = successorNode;
		}

		// 删除node节点（node的度必然是1或者0）
		Node<E> replacementNode = node.left != null ? node.left : node.right;

		// node拥有左子节点/右子节点,为度为1的节点.
		if (replacementNode != null) {
			// 更改parent
			replacementNode.parent = node.parent;
			if (node.parent == null) { // node为根节点
				root = replacementNode;
			} else {
				// node是父节点的左子节点,那么就讲父节点的左子节点替换为当前节点的子节点.
				if (node == node.parent.left) {
					node.parent.left = replacementNode;
				} else {
					node.parent.right = replacementNode;
				}
			}
			
			// 删除节点之后的平衡二叉树处理
			afterRemove(node);
			
		// 下面的判断代表node为度为0的叶子节点.
		} else if (node.parent == null) { // node是叶子节点并且是根节点
			root = null;
			// 删除节点之后的平衡二叉树处理
			afterRemove(node);
			
		} else { // node是叶子节点，但不是根节点
			// node是父节点的左子节点,那么就将父节点的左子节点置为null
			if (node == node.parent.left) {
				node.parent.left = null;
			} else {
				node.parent.right = null;
			}
			// 删除节点之后的平衡二叉树处理
			afterRemove(node);
		}
	}

	// 根据元素查找节点
	private Node<E> node(E element) {
		Node<E> node = root;
		while (node != null) {
			int cmp = compare(node.element, element);
			if (cmp == 0) {
				return node;
			} else if (cmp > 0) {
				node = node.left;
			} else {
				node = node.right;
			}
		}
		return null;
	}

	// 比较器
	private int compare(E elementOne, E elementTwo) {
		if (comparator != null) {
			return comparator.compare(elementOne, elementTwo);
		}
		return ((Comparable<E>) elementOne).compareTo(elementTwo);
	}
}
